package net.xdclass.review;

import java.util.Arrays;

/**
 * @Author: wangzhan
 * @Description: TODO
 * @DateTime: 2025/3/1 10:59
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] aa = {1,3,2,-1,9,5};
        sort(aa,0,aa.length-1);
        System.out.println(Arrays.toString(aa));
    }
    private static void sort(int[] array,int start,int end){
        if(start>=end){
            return;
        }
        int index = partition(array, start, end);
        sort(array,start,index-1);
        sort(array,index+1,end);

    }

    private  static  int partition(int[] array,int start,int end){
        //选取第一个元素作为基准值，所有小于这个元素的放在左边，大于这个元素的放在右边
        int pivot = array[start];
        //指针 分割的地方
        int biggest_smallest = start;
        int tmp;
        for (int i = start+1; i <= end ; i++) {
            if(pivot > array[i]){
                biggest_smallest++;
                //将指针指向的位置和i互换
                tmp = array[i];
                array[i] = array[biggest_smallest];
                array[biggest_smallest] = tmp;
                // 3 2 5 1
            }

        }
        array[start] = array[biggest_smallest];
        array[biggest_smallest] = pivot;
        return biggest_smallest;

    }


    private static int quickSort(int[] array, int start, int end){
        int a = array[start];
        int index = start;
        int tmp;
        for (int i=start;i<=end;i++){
            if(array[i]<a){
                index++;
                tmp=array[i];
               array[i]=array[index];
                array[index] = tmp;
            }
        }
        array[start] = array[index];
        array[index]= a;
        return index;
    }
    private static void sort2(int[] array, int start, int end){
        if(start>end){
            return;
        }
        int i = quickSort(array, start, end);
        sort2(array,start,i-1);
        sort2(array,i+1,end);
    }




}
